package com.algrithom.graph.dfs;

/**
 * 深度优先遍历
 *
 * @author think
 * @version 1.0.0
 * @since 2020/3/6
 */
public class Solution1 {
    
    //           x-1,y
    //  x,y-1    x,y      x,y+1
    //           x+1,y
    // 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
    private static final int[][] DIR = {{-1,0},{0,-1},{1,0},{0,1}};
    
    // 标记数组，标记了 grid 的坐标对应的格子是否被访问过
    private boolean[][] marked;
    
    // grid 的行数
    private int rows;
    
    // grid 的列数
    private int cols;
    
    private char[][] grid;
    
    public static void main(String[] args){
        Solution1 solution = new Solution1();
        char[][] grid1 = {{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
        int numIslands1 = solution.numIslands(grid1);
        System.out.println(numIslands1);

        char[][] grid2 = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
        int numIslands2 = solution.numIslands(grid2);
        System.out.println(numIslands2);
    }
    
    /**
     * 岛屿的个数
     *
     * @param grid 岛屿数据结构
     * @return 个数
     */
    public int numIslands(char[][] grid){
        rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        cols = grid[0].length;
        this.grid = grid;
        marked = new boolean[rows][cols];
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果是岛屿中的一个点，并且没有被访问过
                // 就进行深度优先遍历
                if (!marked[i][j] && grid[i][j] == '1') {
                    count++;
                    dfs(i,j);
                }
            }
        }
        return count;
    }
    
    /**
     * 从坐标为 (i,j) 的点开始进行深度优先遍历
     *
     * @param i i
     * @param j j
     */
    private void dfs(int i,int j){
        marked[i][j] = true;
        // 得到 4 个方向的坐标
        for (int k = 0; k < 4; k++) {
            int newX = i + DIR[k][0];
            int newY = j + DIR[k][1];
            // 如果不越界、没有被访问过、并且还要是陆地
            if (inArea(newX,newY) && grid[newX][newY] == '1' && !marked[newX][newY]) {
                dfs(newX,newY);
            }
        }
    }
    
    /**
     * 封装成 inArea 方法语义更清晰
     *
     * @param x x
     * @param y y
     * @return 状态
     */
    private boolean inArea(int x,int y){
        // 等于号不要忘了
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}
